package algorithm.middle;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-03-07 11:36
 * @Description: 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
 * <p>
 * 返回 s 所有可能的分割方案。
 * <p>
 * 示例:
 * <p>
 * 输入: "aab"
 * 输出:
 * [
 * ["aa","b"],
 * ["a","a","b"]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/palindrome-partitioning
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Partition131 {


    public static void main(String[] args) {
        System.out.println(new Partition131().partition("aaba"));
    }

    //回溯 递归
    public List<List<String>> partition(String s) {
        ArrayList<List<String>> res = new ArrayList<>();
        fun(s,res,new ArrayList<String>() );
        return res;
    }

    public  void fun(String s, List<List<String>> res,List<String> path) {
        if (s.length()==0){
            res.add(path);
            //法2 可以保持path不变，不用每次复制，只用最后一次复制保存
            //res.add(new ArrayList<>(path));
        }
        for (int i = 1; i <= s.length(); i++) {
            String pre = s.substring(0, i);
            if (isHuiwen(pre)){
                //如果前缀是回文的
                //这个list是copy自path的，不能让path被改变了
                ArrayList<String> list = new ArrayList<>(path);
                list.add(pre);
                fun(s.substring(i), res,list);
//                path.add(pre);
//                fun(s.substring(i), res,path);
//                path.remove(path.size()-1);
            }else {
                //如果前缀是不回文的
                continue;
            }
        }
    }

    public boolean isHuiwen(String text) {
        int length = text.length();
        for (int i = 0; i < length / 2; i++) {
            if (text.toCharArray()[i] != text.toCharArray()[length - i - 1]) {
                return false;
            }
        }
        return true;
    }

    //利用动态规划做状态转移方程
    public List<List<String>> 动态规划(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        char[] charArray = s.toCharArray();
        // 预处理
        // 状态：dp[i][j] 表示 s[i][j] 是否是回文
        boolean[][] dp = new boolean[len][len];
        // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
        for (int right = 0; right < len; right++) {
            // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
            for (int left = 0; left <= right; left++) {
                if (charArray[left] == charArray[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
                    dp[left][right] = true;
                }
            }
        }

        Deque<String> stack = new ArrayDeque<>();
        dfs(s, 0, len, dp, stack, res);
        return res;
    }

    private void dfs(String s, int index, int len, boolean[][] dp, Deque<String> path, List<List<String>> res) {
        if (index == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < len; i++) {
            if (dp[index][i]) {
                path.addLast(s.substring(index, i + 1));
                dfs(s, i + 1, len, dp, path, res);
                path.removeLast();
            }
        }
    }

}
